Automated production lines often employ imaging technology to assist in examining parts or other objects being produced. Imaging technologies commonly utilized on such production lines can include, for example, video imaging, digital photography, and/or other known processes. Typically, known imaging technologies are used to obtain images of such manufactured items within a field of view, and each image may contain a number of geometric contours. Such contours may be, for example, machined surfaces, holes, corners, and/or other tightly-toleranced portions of the fabricated items. These known technologies acquire an image showing the area of interest and may determine, based on the image, whether aspects of the imaged area fall within an acceptable range for the manufactured item. For example, such imaging technologies may be used in high-speed manufacturing lines to examine the parts or other items being produced, and to assist in rejecting parts that are out of tolerance and/or otherwise unacceptable.
In some imaging applications, however, the area of interest may be larger than the field of view of the imaging device. For example, a digital camera or other imaging device used to inspect and/or examine the manufactured items discussed above may have a relatively small field of view, and this field of view may be too small to capture an image of an entire machined surface of the item. In such applications, the area of interest may extend across the boundary of one field of view and into another field of view.
To compensate for the limited field of view associated with known imaging devices, or for the positioning of areas of interest across the boundaries of two adjacent images, imaging devices commonly capture multiple images of the item being examined from multiple fields of view and then combine the corresponding or overlapping portions of the images using digital combination software or other means. The process of combining images from different fields of view is sometimes called “image stitching”. However, a great deal of inaccuracy can be introduced when combining images from the different fields of view using known stitching techniques. In addition, such methods commonly require a large amount of computer and/or processor capacity or speed, and can be extremely cumbersome from an operational standpoint.
For example, the images obtained by prior art systems are typically “binary” pixel-based images. Such images are made up of a group of screen pixels that are either on or off. A prior art system may obtain multiple pixel-based images of the region being inspected and, to ensure that the entire region is captured, such systems may overlap the fields of view for each image. For instance, after a first image of the area of interest is taken, such systems may take a second (adjacent) image of the same area wherein the field of view of the second image overlaps the field of view of the first image. Then the first image and the second image are merged or “stitched” together, pixel by pixel.
However, although in the real world each contour of a machined part has a distinct boundary, a first pixel-based image of a contour obtained by prior art systems may have slightly different boundary dimensions or configurations than a second (adjacent) pixel-based image of the same contour. For example, a pixel that is turned “on” in the first contour image may be turned “off” in the second contour image. Such pixel to pixel variations between two adjacent images of the same contour can be caused by a number of factors including, but not limited to, slight camera rotation, imperfect calibration of pixel sizes, and inhomogeneous lighting and shading effects causing some pixels in the binary images to be on in one image and off in the other image. When forming a combined image of the contour, prior art stitching methods typically mask these inaccuracies through alignment and interpolation techniques in which the corresponding pixels in the two images are merged.
Unfortunately, known stitching methods are time-consuming, and create potentially massive images requiring a great deal of computer memory to store and analyze. The inaccuracies inherent in known stitching methods may also have a snowball effect if the resulting combined image is later used in comparison analyses with other images. The pixel to pixel variations and onerous memory requirements of known image combination methods can dramatically reduce the efficiency of a manufacturing line, and may require oversight by one or more human operators. Such deficiencies can be quite costly in many high-speed manufacturing environments.
In a paper entitled “Image Alignment and Stitching”, published in Foundations and Trends in Computer Graphics and Computer Vision, 2(1), December 2006, Szeliski discusses additional problems associated with prior art methods such as the unreliability of fully automated stitching. Szeliski points out that it is difficult to simultaneously avoid matching spurious features or repeated patterns while also being tolerant of large outliers. Another common problem Szeliski describes is “parallax error”, the apparent displacement or difference of orientation of an object viewed along two different lines of sight. The stitching deficiencies discussed in Szeliski greatly limit the accuracy, reliability, and speed of existing combination methods used in automated industrial inspection. Although Szeliski also teaches techniques used to correct image distortions caused by parallax error, such correction techniques are not adequate for most high-precision measurement processes.
U.S. Pat. No. 5,371,810 to Vaidyanathan discloses a method of registering perimeter points with X, Y Cartesian coordinates and with eight-bit direction code values. Vaidyanathan also discloses a sorting method used to determine the linking and connectivity relationship between perimeter points. Vaidyanathan's method of sorting perimeter points fails in complex image merging applications, however, because two-dimentional X, Y coordinates of closed feature perimeters cannot both be monotonic. In addition, the Vaidyanathan method fails to sort all perimeter points uniquely in situations where there are two or more perimeter points having the same X or Y coordinate values. In addition, the precision of Vaidyanathan's method is limited to pixel resolution because the method and final results taught therein are pixel-based.
U.S. Pat. No. 4,493,105 to Beall discloses a method of sorting points similar to that of Vaidyanathan. Beall's approach also fails because two-dimensional X, Y coordinates of closed feature perimeters cannot both be monotonic at the same time. Beall's method is also limited to pixel resolution because the method and its final results are pixel-based. Although Beall does mention feature merging, all of Beall's disclosed methods deal only with simple merging cases. The Beall approach fails in complex merging situations, such as when two features overlap or cross at more than two locations, thereby creating multiple combined feature paths. In addition, neither Vaidyanathan nor Beall teach a method of automatically distinguishing a “simple” feature from a “hole” feature.
Accordingly, the present disclosure is directed towards overcoming problems encountered when one attempts to combine two or more images of a feature that is larger than one field of view. The present disclosure is also directed toward overcoming difficulties associated with combining two or more lists of features.